package com.leetcode.study;

/**
 * 快速排序 <br/>
 * 含义：随机选定一个随机的基准数，然后比较，使比基准数大的数据都在基准数的右侧，比基准数小的数都在
 * 基准数左侧，这样就确定了基准数的大小位置，然后再比较剩下部分（还剩下两个部分）同刚开始一样，确定基准数的位置，
 * 等所有的基准数的位置都确定好了，那顺序大小即确定了。<br/>
 *
 * https://blog.csdn.net/weixin_60263012/article/details/127351679，
 * 这个链接给出应该是最初的快速排序，通过左右指针同时操作来完成。
 * 下面的代码是基于文心改版的，代码时间复杂度相对降低了为O(n)
 *
 */
public class QuickSort {


    public static void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private static void quick(int[] arr, int left, int right) {

        // 递归终止
        if(left >= right) {
            return;
        }

        int pivot = partition1(arr,left,right);

        // 比较左边
        quick(arr, left, pivot - 1);
        // 比较右边
        quick(arr, pivot + 1, right);
    }


    private static int partition0(int[] arr, int low, int high) {
        // 选择数组的最后一个元素作为基准值
        int pivot = arr[high];

        // 基准值所在的下标：这个小标i其实就是左边已经比较过小于基准值的下标
        int i = low;

        // 遍历数组，将小于基准值的元素放到左边，大于基准值的元素放到右边
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }

        // 将基准元素放到正确的位置，这个时候左边已经是全部比完的比基准值小的数据了
        // 因为做过了i++，其实这个i就是基准值所在的下标，因为随机选择了第一个值为基准值
        // 所以要和第一个值做互换
        int temp = arr[i];
        arr[i] = arr[high];
        arr[high] = temp;

        return i;
    }

    private static int partition1(int[] arr, int low, int high) {
        // 选择数组的第一个元素作为基准值
        int pivot = arr[low];

        // 基准值所在的下标，从最右边比
        int i = high;

        // 遍历数组，将大于基准值的元素都放到右边，小于基准值的元素放到左边
        // [100, 67, 48, 22, 12, 65, 30, 54, 49, 35, 54] , 基准值 100
        for (int j = high; j > low; j--) {
            if (arr[j] > pivot) {
                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i--;
            }
        }

        // 将基准元素放到正确的位置
        int temp = arr[i];
        arr[i] = arr[low];
        arr[low] = temp;

        return i;
    }

    public static void main(String[] args) {
        int[] arr = {54,32,67,45,65,12,14};
        quickSort(arr);

        // 输出排序后的数组
        for (int val : arr) {
            System.out.print(val + " ");
        }
    }
}
